Critical connections in a network [Tarjan’s Alg, Bridge Finding Alg]

Time: O(|V|+|E|); Space: O(|V|+|E|); hard

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order,

but you should guarantee that for each connections, when you return, index1 is less than index 2.

For instance, if the answer is [[1,2],[3,4]] you can return [[3,4],[1,2]], but [[2,1],[3,4]] is invaild.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: [[1,3]] or [[3,1]]

Constraints:

  • 1 <= n <= 10^5

  • n-1 <= len(connections) <= 10^5

  • connections[i][0] != connections[i][1]

  • There are no repeated connections.

1. Variant of Tarjan’s algorithm

See: https://www.geeksforgeeks.org/bridge-in-a-graph/

[5]:

class Solution1(object):
    """
    Time: O(|V|+|E|)
    Space: O(|V|+|E|)
    """
    def criticalConnections(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: List[List[int]]
        """
        def dfs(edges, parent, u, idx, lowlinks, lookup, result):
            if lookup[u]:
                return
            lookup[u] = True
            curr_idx = lowlinks[u] = idx[0]
            idx[0] += 1

            for v in edges[u]:
                if v == parent:
                    continue
                dfs(edges, u, v, idx, lowlinks, lookup, result)
                lowlinks[u] = min(lowlinks[u], lowlinks[v])
                if lowlinks[v] > curr_idx:
                    # if any lowlink of neighbors is larger than curr_idx
                    result.append([u, v])

        edges = [[] for _ in range(n)]
        idx, lowlinks, lookup = [0], [0]*n, [False]*n
        result = []
        for u, v in connections:
            edges[u].append(v)
            edges[v].append(u)

        dfs(edges, -1, 0, idx, lowlinks, lookup, result)

        return result

[6]:

s = Solution1()

n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]
assert s.criticalConnections(n, connections) == [[1,3]]